package 算法.LeetCode91.基础篇01;

import java.util.Arrays;

/**
 * @author: 谢君臣
 * @create: 2021-02-01 20:48
 * @founction: XXXX
 *给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * 输入：nums = [2,0,2,1,1,0]
 * 输出：[0,0,1,1,2,2]
 */
public class LC75 {
    public static void main(String[] args) {
        sortColors(new int[]{1,0,1});
    }
    public static void sortColors(int[] nums) {
        int i=0,j=nums.length-1;
        while (i<j){
            while (i<nums.length&&nums[i]<1)i++;
            while (j>=0&&nums[j]>1)j--;
            if (i==j||i>j||j<i)
                break;
            if (nums[i]==nums[j]){
                int t= i+1;
                while (t<j){
                    if (nums[t]<nums[i]||nums[t]>nums[j]){
                        sump(nums,i,t);
                        break;
                    }
                    t++;
                }
                if (t==j)
                    break;
            }
            else {
                sump(nums,i,j);
            }
        }
        System.out.println(Arrays.toString(nums));
    }
    private static void sump(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i]= nums[j];
        nums[j]= temp;
    }

    public static void test(){
        int []nums = {1,0,2,0,1};
        int a=0,b=0,c=0,i=0;
        for(i = 0;i<nums.length;i++){
            if(nums[i]==0)
                a++;
            else if(nums[i]==1)
                b++;
            else
                c++;
        }
        i=0;
        while(a>0){
            nums[i++]=0;
            a--;
        }while(b>0){
            nums[i++]=1;
            b--;
        }while(c>0){
            nums[i++]=2;
            c--;
        }
        System.out.println(Arrays.toString(nums));
    }

}
